package com.future;

/**
 * Description: 680. 验证回文串 II
 * 给你一个字符串 s，最多 可以从中删除一个字符。
 * <p>
 * 请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。
 *
 * @author weiruibai.vendor
 * Date: 2022/11/17 10:12
 */
public class Solution_680 {

    static private Solution_680 instance = new Solution_680();

    public static void main(String[] args) {
        String s = "abca";
        //s = "aba";
        s = "abaavba";
        //s = "ebcbb e cecabbacec bbcbe";
        s = "ebcbbececabbacecbbcbe";
        System.out.println(instance.validPalindrome(s));
    }

    public boolean validPalindrome(String s) {
        if (s.length() == 1) {
            return true;
        }
        int N = s.length();
        int deleteCount = 0;
        // 两边向中间
        int L = 0;
        int R = N - 1;
        return validIsPalindrome(s, L, R, deleteCount);

    }

    private boolean validIsPalindrome(String s, int L, int R, int deleteCount) {
        while (L <= R) {
            if (s.charAt(L) == s.charAt(R)) {
                L++;
                R--;
            } else {
                if (deleteCount > 1) {
                    return false;
                }
                // 重新调整
                return validIsPalindrome(s, L, R - 1, deleteCount + 1) || validIsPalindrome(s, L + 1, R, deleteCount + 1);
            }
        }
        if (deleteCount > 1) {
            return false;
        }
        return true;
    }


}
